<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /* 
      这题有个细节在于：它求的是根节点到叶子节点的最短路径，必须是到叶子节点！！
      思路：①dfs 找出到叶子节点的所有路径，然后计算最小值
      */
      let tree = {
        val: 1,
        left: {
          val: 2,
          left: {
            val: 4,
          },
          right: {
            val: 5,
          },
        },
        right: {
          val: 3,
          left: {
            val: 6,
          },
          right: {
            val: 7,
          },
        },
      }
      var minDepth = function (root) {
        let result = []
        function dfs(root, path) {
          //确定终止条件
          if (!root) return null
          path.push(root.val)
          if (!root.left && !root.right) {
            return result.push([...path])
          }
          //确定递归元素，选择对应元素  如果是多叉树，就可以使用for循环
          if (root.left) {
            dfs(root.left, path)
            path.pop()
          }
          if (root.right) {
            dfs(root.right, path)
            path.pop()
          }
        }
        dfs(root, [])
        let min = Infinity
        for (let i = 0; i < result.length; i++) {
          min = Math.min(result[i].length)
        }
        return min == Infinity ? 0 : min
      }
      console.log(minDepth(tree))
    </script>
  </body>
</html>
